#include "mySearch.h"
#include <iostream>
#include <string>


using namespace std;

//默认构造函数
SSTable::SSTable()
{
    length=0;
    origin=nullptr;
}

//带参构造函数
SSTable::SSTable(int len,int* arr)
{
    length=len;     //设置元素个数
    origin=new int[length];
    for(int i=0;i<length;i++)
    {
        origin[i]=arr[i];   //将输入数组的元素复制到顺序查找表中
    }
}

//析构函数
SSTable::~SSTable()
{
    delete[] origin;
}

//辅助函数：获取元素个数
int SSTable::getLength()
{
    return length;
}

//辅助函数：获取元素数组
int* SSTable::getOrigin()
{
    return origin;      //返回元素数组的指针
}

//辅助函数：设置元素个数
void SSTable::setLength(int len)
{
    length=len;
}

//辅助函数：设置元素数组
void SSTable::setOrigin(int* arr)
{
    //若之前已分配过内存，则先将其释放
    if(origin!=nullptr)
    {
        delete[] origin;
    }
    origin=new int[length];
    for(int i=0;i<length;i++)
    {
        origin[i]=arr[i];
    }
}

//实现折半查找，返回元素的下标（从0开始），不存在返回-1
int SSTable::binSearch(int val)
{
    int start=0;
    int end=length-1;
    //当val小于数组中间元素时，val在左半部分，更新end
    //当val大于数组中间元素时，val在右半部分，更新start
    //不断进行val和数组中间元素的比较，直到val==[mid]，查找成功或start>end退出循环，查找失败
    while(start<=end)
    {
        int mid=start+(end-start)/2;
        if(val<origin[mid])
        {
            end=mid-1;
        }
        else if(val>origin[mid])
        {
            start=mid+1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

//节点类的默认构造函数
BSTreeNode::BSTreeNode():data(0),lchild(nullptr),rchild(nullptr){}

//节点类的带参构造函数
BSTreeNode::BSTreeNode(int value):data(value),lchild(nullptr),rchild(nullptr){}

BSTreeNode::BSTreeNode(int value, BSTreeNode* left, BSTreeNode* right)
    :data(value),lchild(left),rchild(right){}

//节点类的析构函数
BSTreeNode::~BSTreeNode() {}

//辅助函数：获取节点值
int BSTreeNode::getData()
{
    return data;
}

//辅助函数：获取左子节点
BSTreeNode* BSTreeNode::getLChild()
{
    return lchild;
}

//辅助函数：获取右子节点
BSTreeNode* BSTreeNode::getRChild()
{
    return rchild;
}

//辅助函数：设置节点值
void BSTreeNode::setData(int value)
{
    data=value;
}

//辅助函数：设置左子结点
void BSTreeNode::setLChild(BSTreeNode* left)
{
    lchild=left;
}

//辅助函数：设置右子节点
void BSTreeNode::setRChild(BSTreeNode* right)
{
    rchild=right;
}

//二叉排序树类的默认构造函数
BSTree::BSTree():num(0),root(nullptr) {}

//二叉排序树类的带参构造函数
BSTree::BSTree(int number, int* data):num(0),root(nullptr)
{
    for(int i=0;i<number;i++)
    {
        addNode(data[i]);   //添加节点
    }
}

//二叉排序树类的析构函数
BSTree::~BSTree()
{
    deleteTree(root);
}

void BSTree::deleteTree(BSTreeNode* node)
{
    if(node==nullptr)   return;
    deleteTree(node->getLChild());  //递归释放左子树
    deleteTree(node->getRChild());  //递归释放右子树
    delete node;    //释放当前节点
}

//辅助函数：获取节点个数
int BSTree::getNum()
{
    return num;
}

//辅助函数：获取根节点
BSTreeNode* BSTree::getRoot()
{
    return root;
}

//辅助函数：设置根节点
void BSTree::setNum(int count)
{
    num=count;
}

//辅助函数：设置根节点
void BSTree::setRoot(BSTreeNode* rootNode)
{
    root=rootNode;
}

//前序遍历递归调用
void printTemp(BSTreeNode* node, string& result)
{
    if(node==nullptr)   return;
    result+=to_string(node->getData()) +" ";
    printTemp(node->getLChild(),result);
    printTemp(node->getRChild(),result);
}

string BSTree::printTree()
{
    string result;
    printTemp(root,result);
    return result;
}

//排序树查找，找到返回true，未找到返回false
//从根节点开始查找，若小于当前节点则查找左子树，大于则查找右子树
//直至找到返回true或未找到退出while循环返回false
bool BSTree::searchNode(int val)
{
    BSTreeNode* current=root;
    while(current!=nullptr)
    {
        if(current->getData()==val)
        {
            return true;
        }
        else if(current->getData()>val)
        {
            current=current->getLChild();
        }
        else
        {
            current=current->getRChild();
        }
    }
    return false;
}

//排序树添加节点
bool BSTree::addNode(int val)
{
    if(searchNode(val))
    {
        return false;       //若节点已存在，直接返回
    }

    BSTreeNode* newNode=new BSTreeNode(val);
    //若当前树为空，则新节点作为根节点
    if(root==nullptr)
    {
        root=newNode;
    }
    else
    {
        BSTreeNode* current=root;   //当前节点
        BSTreeNode* prev=nullptr;   //当前节点的父节点，即插入位置父节点

        while(current!=nullptr)
        {
            prev=current;
            if(val<current->getData())
            {
                current=current->getLChild();
            }
            else
            {
                current=current->getRChild();
            }
        }

        //插入新结点
        if(val<prev->getData())
        {
            prev->setLChild(newNode);
        }
        else
        {
            prev->setRChild(newNode);
        }
    }
    num++;
    return true;
}

//排序树删除节点，删除成功返回true，所删除的节点不存在返回false
bool BSTree::deleteNode(int val)
{
    BSTreeNode* parent=nullptr;     //当前节点的父节点
    BSTreeNode* current=root;       //当前节点 从根节点开始

    //定位要删除节点及其父节点
    while(current!=nullptr&&current->getData()!=val)
    {
        parent=current;
        if(val<current->getData())
        {
            //若查找值小于当前节点，则继续向左子树查找
            current=current->getLChild();
        }
        else
        {
            //若大于则向右子树移动
            current=current->getRChild();
        }
    }

    //若从while循环中退出但current值为空，则证明未找到要删除节点
    if(current==nullptr)
    {
        return false;
    }

    //case1:当前节点为叶子结点
    if(current->getLChild()==nullptr&&current->getRChild()==nullptr)
    {
        if(current==root)
        {
            //若当前节点为根节点，则删除后树为空
            delete current;
            root=nullptr;
        }
        else if(parent->getLChild()==current)
        {
            //若要删除节点位于左子树上
            parent->setLChild(nullptr);
        }
        else
        {
            //要删除节点位于右子树上
            parent->setRChild(nullptr);
        }
    }

    //case2:当前节点只有一个子节点
    else if(current->getLChild()==nullptr||current->getRChild()==nullptr)
    {
        BSTreeNode* child=(current->getLChild()==nullptr)?current->getRChild():current->getLChild();
        if(current==root)
        {
            //若要删除根节点，则更新根节点为孩子
            root=child;
        }
        else if(parent->getLChild()==current)
        {
            //若要删除左节点，将parent左指针更新
            parent->setLChild(child);
        }
        else
        {
            //若要删除右节点，将parent右指针更新
            parent->setRChild(child);
        }
        delete current;
    }

    //case3:当前节点有两个子节点,此时用右子树中最小节点和当前节点互换
    else
    {
        BSTreeNode* minParent=current;      //右子树中最小节点的父节点
        BSTreeNode* minNode=current->getRChild();   //从当前节点右子树开始寻找最小节点

        while(minNode->getLChild()!=nullptr)
        {
            minParent=minNode;
            minNode=minNode->getLChild();       //一路向左至右子树最左节点即为最小
        }

        //用最小节点值覆盖要删除节点值
        current->setData(minNode->getData());

        //删除最小节点
        if(minParent->getLChild()==minNode)
        {
            minParent->setLChild(minNode->getRChild());
        }
        else
        {
            minParent->setRChild(minNode->getRChild());
        }
        delete minNode;
    }
    num--;
    return true;
}
